Geocoding is a known technique whereby a human referencing system for physical locations, such as a street address, country and/or postcode is converted into associated geographic coordinates, e.g. latitude and longitude. Various different geocoding systems currently exist and rely, at least to some extent, on a geographic information system (GIS) in which the street network is already mapped within the geographic coordinate space. Inverse geocoding is the reverse process.
Any modern digital map (or mathematical graph, as they are sometimes known) can be considered as a GIS, and in a most simple form is effectively a database consisting of a plurality of tables defining firstly nodes (which can be considered as points or zero-dimensional objects) most commonly representative of road intersections, and secondly lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node, which may be the same in the case of a segment of zero length or a looped segment (in which case the segment has a non-zero length), but are more commonly separate. Nodes may be considered real or “valid” for the purposes of this application when they represent a road intersection at which a minimum of 3 lines or segments intersect, whereas “artificial” or “avoidable” nodes are those which are provided as anchors for segments not being defined at one or both ends by a real node. These artificial nodes are useful in digital maps to provide, among other things, shape information for a particular stretch of road.
In this manner, nodes, lines and segments can be used as a means of completely describing a road network, and each element in the database is further defined by various attributes which are again represented by data in the tables of the database, e.g. each node will typically have latitude and longitude attributes to define its real-world position. The complete “graph” of the road network is described by millions of nodes and segments to cover an area of spanning one or more countries, or part thereof.
Although practically all modern digital maps involve a structured definition of nodes and segments, the actual manner in which this is effected between digital map providers varies enormously. For instance, each map vendor (and possibly each map version) may use unique IDs for each map element, whether node or segment. Therefore, even simple geocoding and inverse geocoding is possible only with some knowledge of the underlying structure of the database in which the requisite digital map is embodied. More simply, a query designed to extract a street address from one digital map database based on latitude and longitude will not necessarily work on another—it may need re-casting as appropriate for the particular digital map database in question. This can also be true for different versions of a digital map provided by the same vendor.
One particular attribute often included in digital map databases is a Traffic Message Channel (TMC) location table reference. TMC is a technology for delivering traffic and travel information to vehicle users, and more particularly to navigation systems (either portable or integrated) present within those vehicles and which include some form of digital map. A TMC message consists of an event code (which need not be traffic-specific, although these are most common) and a location code, often consisting of an ordered list of location references by means of which the location of the traffic event can be determined in the digital map and thus represented graphically on the screen of the navigation system. A number of pre-defined nodes in the digital map are assigned a TMC location reference which is determined with reference to a limited location table. The location table consists of 216 (65536) location references corresponding to a similar number of physical or real world locations, usually road intersections, also identifiable in the digital map.
Although TMC messages are very efficient in that they can be as short as 37 bits in length and therefore do not impinge significantly on available bandwidth for broadcast data, only a fixed number of location references are available, and therefore typically only motorways and major highways (or intersections thereon) in each country offering TMC can be referenced. There are various other disadvantages of TMC location references. For instance, TMC location tables are                often maintained through a public authority or National Government,        prone to change between update cycles, which are traditionally quite long,        non-existent, or available only commercially, in some markets.        
As it is becoming possible to identify traffic build up on secondary and urban roads using GSM and GPS probe data (e.g. vehicles users increasingly possess either a mobile phone or a connected satellite navigation devices useful as probes), a more expansive referencing system is required.
One attempt to overcome some of the drawbacks of TMC location references or map-specific references is the Dynamic Location Referencing project, also known as AGORA-C (in the process of standardization under no. ISO 17572-1,2, and 3). Although a complete description of the AGORA-C location referencing approach is beyond the scope of this application, the fundamentals of the approach are that a location reference can be completely specified by a set of location points, specified by coordinate pairs of latitude and longitude and ordered in a list, each point complying with various rules but most importantly being consecutive in terms of the location being referenced and the previous point in the list, i.e. successive points form a next-point-relationship. As with other location referencing systems, each point is provided with a number of attributes which assist in better defining that point, but specific to the AGORA-C method is the identification of each point as one of a location point, an intersection point, a routing point, or some combination of these three. Each point along the location at which the road section signature changes is represented by an intersection point, so locations being paths over a road network and which pass through intersections without any road section signature change need not be referenced by an intersection point. For example, if a location includes a section of motorway which includes junctions that are not relevant as far as the location is concerned, then there is no need to include intersection points for such junctions.
One of the earlier steps in the AGORA-C encoding method is the determination of all intervening intersection points between a first and a last intersection point along the location at which a change of road section signature occurs. All these points are added to a table of points ultimately forming part of the AGORA-C location reference. Within this table, at least two routing points will also have been identified, again according to certain rules. Routing points are points used to reconstruct the location (in a decoding operation) by route calculation and are provided only where road segments having a routing point bearing attribute are longer than a certain length. During the encoding process according to the AGORA-C standard, a determination is made as to whether intermediate routing points are required to calculate a route from the first identified routing point to the last identified routing point. This determination is made using a weighted shortest path algorithm—if it is determined that additional routing points are required, then these are also added to the pre-existing table of intersection points, but only in instances where such points do not coincide with the previously identified intersection points. In this latter case, a simple attribute change is required to ensure that the pre-existing intersection point is also identified as a routing point. Although in most cases, no additional routing points may be required, it is to be noted that the effect of the weighted shortest path algorithm as applied in AGORA-C is to potentially increase the number of points required, as opposed to reducing the number of pre-existing intersection points by which the location is at first specified.
Although this referencing approach is comprehensive in that it is possible to accurately and repeatably encode and decode any location existing within a geographical information system, it is believed that that the system is excessive and possibly redundant in certain aspects, and a more efficient encoding system is possible. For instance, although the referencing method is independent of any pre-compilation work and is map-independent, the average AGORA-C message size is significantly higher than 30 bytes per location reference which may be problematical if not prohibitive in the modern climate of highly congested transmission frequencies and the increasingly restricted bandwidths associated therewith, particularly as regards mobile/wireless devices to which it may be desired to transmit such information.
It is therefore an object of this invention to provide an efficient and compact format for a location reference which:                is more efficient than AGORA-C without significantly compromising on accuracy,        is not prejudicial to available bandwidths for broadcast data,        is capable of accounting for differences in the underlying digital map (or differences between versions thereof) used in creating the reference        can be a complete substitute for the TMC location referencing system        is capable of addressing the entire road network including urban and low-level roads of any country for which a digital map is available, and        does not require periodic maintenance.        